package top.huhuiyu.ds.find;

/**
 * 在数组中查找find所在的索引位置,找不到就返回-1
 * 
 * @author Aiden Pearce
 *
 */
public class FindUtil {
  public static int searh(int[] array, int find) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == find) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 对分搜索，要求必须是有序的数据
   * 
   * @param array
   * @param find
   * @return
   */
  public static int binarySearch(int[] array, int find) {
    int start = 0;
    int end = array.length - 1;
    int mid;
    while (start <= end) {
      // 中分
      mid = (start + end) / 2;
      // 找到的情况
      if (array[mid] == find) {
        return mid;
      }
      // 上半区查找（find比中值小）
      if (find < array[mid]) {
        end = mid - 1;
      }
      // 下半区查找(find比中值大)
      if (find > array[mid]) {
        start = mid + 1;
      }
    }
    return -1;
  }
}
